package com.lry.basic.algorithm.graph;

import java.util.*;

public class SlidingPuzzle {

    int m=3;
    int n=3;
    Map<String,String> pre = new HashMap<>();
    String end = null;
    String initState;

    public int slidingPuzzle(int[][] board) {
        Queue<String> queue = new LinkedList<>();
        //<"123540",0>value是步数
        Map<String,Integer> visited = new HashMap<>();

        initState = boardToStr(board);
        if(initState.equals(endStr())){
            end = initState;
            return 0;
        }
        queue.offer(initState);
        visited.put(initState,0);

        while(!queue.isEmpty()){
            String curStr = queue.poll();
            List<String> nextList = getNext(curStr);
            for(String next:nextList){
                if(!visited.containsKey(next)){
                    visited.put(next,visited.get(curStr)+1);
                    queue.offer(next);
                    //保存路径
                    pre.put(next,curStr);
                    if(next.equals(endStr())){
                        end = next;
                        return visited.get(next);
                    }
                }
            }
        }
        return -1;
    }

    private String endStr(){
        int mn = m*n;
        StringBuilder sb = new StringBuilder();
        for(int i=1;i<mn;i++){
            sb.append(i);
        }
        sb.append(0);
        return sb.toString();
    }

    private List<String> getNext(String curStr) {
        List<String> res = new ArrayList<>();
        int[][] board = strToBoard(curStr);

        int zero = 0;
        for(;zero<curStr.length();zero++){
            if(board[zero/n][zero%n]==0)break;
        }
        int zeroX = zero/n;
        int zeroY = zero%n;

        for(int i=-1;i<=1;i++){
            for(int j=-1;j<=1;j++){
                if(i==0||j==0){
                    int x = zeroX+i;
                    int y = zeroY+j;
                    if(inArea(x,y)){
                        swap(board,zeroX,zeroY,x,y);
                        res.add(boardToStr(board));
                        swap(board,zeroX,zeroY,x,y);
                    }
                }
            }
        }
        return res;
    }

    private Iterable<String> path(){
        List<String>res = new ArrayList<>();
        if(end==null){
            return res;
        }
        String cur = end;
        while(cur!=initState){
            res.add(0,cur);
            cur = pre.get(cur);
        }
        res.add(0,initState);
        return res;
    }

    private void swap(int[][] board, int zeroX, int zeroY, int x, int y) {
        int t = board[zeroX][zeroY];
        board[zeroX][zeroY] = board[x][y];
        board[x][y] = t;
    }

    private boolean inArea(int x, int y) {
        return x>=0&&x<=m-1&&y>=0&&y<=n-1;
    }

    private int[][] strToBoard(String curStr){
        int[][] board = new int[m][n];
        for(int i=0;i<curStr.length();i++){
            board[i/n][i%n] = curStr.charAt(i)-'0';
        }
        return board;
    }

    private String boardToStr(int[][] board){
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                sb.append(board[i][j]);
            }
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        SlidingPuzzle puzzle = new SlidingPuzzle();
        System.out.println(puzzle.slidingPuzzle(new int[][]{{4,1,2},{5,0,3},{6,7,8}}));
        System.out.println(puzzle.path());
    }
}
